package fun.coding.leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class CloneGraph {

	public static void main(String[] args) {
		CloneGraph ins = new CloneGraph();
		UndirectedGraphNode root = new UndirectedGraphNode(-1);
		UndirectedGraphNode r2 = new UndirectedGraphNode(1);
		root.neighbors.add(r2);
		
		UndirectedGraphNode newRoot = ins.cloneGraph(root);
	}
	
	// Still DFS, but without using recursion
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if (node == null) return null;
		
		Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>();
		Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
		
		stack.push(node);
		map.put(node, new UndirectedGraphNode(node.label));
		
		while (!stack.isEmpty()) {
			UndirectedGraphNode cur = stack.pop();
			
			for (UndirectedGraphNode n : cur.neighbors) {
				UndirectedGraphNode copyNeighbor = null;
				
				if (map.containsKey(n)) {
					copyNeighbor = map.get(n);
				} else {
					copyNeighbor = new UndirectedGraphNode(n.label);
					map.put(n, copyNeighbor);
					stack.push(n);
				}
				
				map.get(cur).neighbors.add(copyNeighbor);
			}
		}
		
		return map.get(node);
	}
	
	
	// This is DFS, just like cloning a tree, only difference is need to avoid a node's neighbor is itself, that's why need a map
	public UndirectedGraphNode cloneGraphDFS(UndirectedGraphNode node) {
		Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
		return this.helper(node, map);
	}
	
	private UndirectedGraphNode helper(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
		if (node == null) return null;
		
		if (map.containsKey(node)) return map.get(node);
		
		UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
		map.put(node, copy);
		
		for (UndirectedGraphNode n : node.neighbors) {
			UndirectedGraphNode copyNeighbor = this.helper(n, map);
			copy.neighbors.add(copyNeighbor);
		}
		
		return copy;
	}
	
	// http://blog.csdn.net/linhuanmars/article/details/22715747
	public UndirectedGraphNode cloneGraphBFS(UndirectedGraphNode node) {
		if (node == null) return null;
		Map<UndirectedGraphNode, UndirectedGraphNode> lookup = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
		Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
		
		q.offer(node);
		lookup.put(node, new UndirectedGraphNode(node.label));
		
		while (!q.isEmpty()) {
			// the nodes in the queue has been visited before
			UndirectedGraphNode cur = q.poll();
			
			for (UndirectedGraphNode it : cur.neighbors) {
				UndirectedGraphNode copyNeighbor = null;
				
				if (lookup.containsKey(it)) {
					copyNeighbor = lookup.get(it);
				} else {
					copyNeighbor = new UndirectedGraphNode(it.label);
					lookup.put(it, copyNeighbor);
					q.offer(it);
				}
				lookup.get(cur).neighbors.add(copyNeighbor);
			}
		}
		// Don't need to keep a boolean, isFirst, that's silly
		return lookup.get(node);
	}

}
